The present invention relates to an apparatus for checking and correcting errors in a memory word consisting of information bits and check bits encoded in a specially structured code. More specifically it relates to apparatus for detecting and correcting single and double errors in a data word, detecting greater than two errors and checking the operations of the apparatus itself for component faults.
It is axiomatic that data entering a data processor, whether it originates in a local memory, or is received from a remote source via a communication link, must be correct. For this reason many error detecting and error correcting codes have been evolved to insure the integrity of the information to be processed. Generic to all of these codes is redundancy, wherein additional bits are added to the information bits as a function thereof to permit the algorithm controlling the check bits to be recomputed at the destination for error detection and possible correction, if the code is sufficiently sophisticated.
One class of codes, known as single error correction, double error detection (SEC/DED) is described by R. W. Hamming in "Error Detecting and Error Correcting Codes", Bell Systems Technical Journal, 29, 1950, pages 147-160. The instant code is a properly chosen variation of that code.
U.S. Pat. No. 3,688,265 issued Aug. 29, 1972 to W. C. Canter et al. discloses a self-checking memory translation system employing a Hamming SEC/DED code.
Another class of codes is the Bose Chaudhuri code and variations thereof by Golay and by Hocquenghem. Examples of these and apparatus for exploiting their error correction capabilities are exemplified in U.S. Pat. No. 3,622,982 issued Nov. 23, 1971 to B. S. Clark Jr. et al., by U.S. Pat. No. 3,418,629 issued Dec. 24, 1968 to R. T. Chien, and by U.S. Pat. No. 3,685,014 issued Aug. 15, 1972 to My-Yue Hsiao et al.
Error correcting code theory and applications are treated in the text "Error Correcting Codes" by W. W. Peterson, published by M. I. T. Press and John Wiley and Sons Inc., 1961.
The correction capabilities of any code is dependent upon redundancy. In the simplest case of a single parity bit, there are no correction possibilities. In fact, two compensating errors will not be detected, as the parity is unchanged. In U.S. Pat. No. 3,622,982, supra, the Golay code employs 12 data bits and 11 check bits for the correction of triple errors. This is a very large redundancy.